package com.zyk.leetcode;

/**
 *
 * https://leetcode-cn.com/problems/number-of-steps-to-reduce-a-number-to-zero/
 *
 * @author zhangsan
 * @date 2021/3/31 9:15
 */
public class C1342 {

    public static int numberOfSteps (int num) {
        int i = 0;
        while (num != 0) {
            if(num % 2 == 0) {
                num >>= 1;
            }else {
                num -= 1;
            }
            i++;
        }
        return i;
    }

    /** 根据计算方式推出, 它二进制有多少个1 + 最左侧的1移动到最右侧要多少布. 就是答案 */
    public static int numberOfSteps2 (int num) {
        int last1Index = 0;
        int count1 = 0;
        for (int i = 0; i <= 31; i++) {
            if((num & (1<<i)) != 0 ) {
                count1++;
                last1Index = i;
            }
        }
        return last1Index + count1;
    }

    public static int numberOfSteps3 (int num) {
        String s = Integer.toBinaryString(num);
        int n = 0;
        for (int i = 0; i < s.length(); i++) {
            if(s.charAt(i) == '1') {
                n++;
            }
        }
        return s.length()-1 + n;
    }

    public static void main(String[] args) {
        numberOfSteps3(22);

        for (int i = 0; i <= 200; i++) {
            System.out.println(i + " : " + numberOfSteps(i));
            System.out.println(i + " : " + numberOfSteps2(i));
        }
    }

}
